package a1_p04_ak_fh;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.jgraph.graph.DefaultEdge;
import org.jgrapht.Graph;
import org.jgrapht.graph.SimpleGraph;

public class BreadthFirstSearch {
	
	/**
	 * Factory method of the class
	 * @param graph
	 * @param startVertex
	 * @param endVertex
	 * @return Way of vertices from the startvertex to the endvertex
	 */
	public static List<String> BFS (Graph<String, DefaultEdge> graph, String startVertex,
			String endVertex) {
		BreadthFirstSearch bfs = new BreadthFirstSearch();
		return bfs.BreathFirstSearch(graph, startVertex, endVertex);
	}
	
	/**
	 * Constructor of the class
	 * @param graph
	 * @param startVertex
	 * @param endVertex
	 * @return Way of vertices from the startvertex to the endvertex
	 */
	private List<String> BreathFirstSearch (Graph<String, DefaultEdge> graph, String startVertex,
			String endVertex) {
		
		// Access value - > access to the graph
		int access =0;

		// Visited Vertices
		Map<String, Integer> visited = new HashMap<String, Integer>();

		// List of Vertices to visit
		List<String> todo = new ArrayList<String>();
		
		// current vertex
		String currentVertex;

		// StartVertex is visited and saved in the list of upcoming vist.
		visited.put(startVertex, 0);
		todo.add(startVertex);

		// while the list of vertices are not empty and the
		while (!todo.isEmpty() && !(todo.get(0).equals(endVertex))) {

			// Get the vertex which are in scope now
			currentVertex = todo.get(0);
			// Remove the vertex because we are using this vertex now
			todo.remove(0);

			//System.out.println("Visiting " + currentVertex);

			// count the access
			access++;
			
			// Go through all edges of this vertex
			for (DefaultEdge edge : graph.edgesOf(currentVertex)) {
				
				// get the target vertex of this edge
				String vertex = graph.getEdgeTarget(edge);
				
				// If the graph is a undirected and the target of the current vertex is the current vertex
				// -> loop
				if(graph instanceof SimpleGraph && vertex.equals(currentVertex)) {
					vertex = graph.getEdgeSource(edge);
				}

				// If the vertex was not visited
				if (!visited.containsKey(vertex)) {

					// Mark the vertex as visited and save the waylength
					visited.put(vertex, visited.get(currentVertex) + 1);

					// Add the vertex to the list -> Upcoming search point
					todo.add(vertex);
				}
				
			}

		}
		
		//System.out.println(visited.toString());
		
		// Search the fast way -> minimum of edges to the endvertex

		// Begin at the End
		List<String> result = new ArrayList<String>();
		currentVertex = endVertex;

		System.out.println("Weglaenge: " + visited.get(currentVertex));
		// Add last vertex
		result.add(currentVertex);

		while (!currentVertex.equals(startVertex)) {

			// Going to each edge of the graph
			for (DefaultEdge edge : graph.edgesOf(currentVertex)) {

				// If the vertex was not visited -> ignore 
				if(visited.containsKey(graph.getEdgeSource(edge))){
					
					// save the source vertex
					String newVertex = graph.getEdgeSource(edge);
					
					// get the waylength
					int edgeValue = visited.get(newVertex);
	
					// is a simple graph and the current vertex has a loop
					if (graph instanceof SimpleGraph
							&& newVertex.equals(currentVertex)) {
						newVertex = graph.getEdgeTarget(edge);
						edgeValue = visited.get(graph.getEdgeTarget(edge));
					}
	
					if (edgeValue == (visited.get(currentVertex) - 1)) {
						// Predecessor Vertex found. This is the new currentVertex
						currentVertex = newVertex;
						
						result.add(0,currentVertex);
					}
				}
			}
		}
		System.out.println(access + " hits\n");
		
		return result;
	}
	
}
